Definition

An α-approximation algorithm for an optimization problem is a polynomial-time algorithm that for all instances of the problem produces a solution whose value is within a factor of α\alpha of the value of an optimal solution.

For an α-approximation algorithm, α\alpha will be called the performance guarantee of the algorithm, in some literature also known as the approximation ratio or approximation factor of the algorithm.

A convention (followed by Williamson & Shmoys) is that α>1\alpha>1 for minimization problems and α<1\alpha < 1 for maximization problem, and thus a 12\frac{1}{2}-approximation algorithm for a maximization problem is a polynomial-time algorithm that always returns a solution whose value is at least half the optimal value.

References

  1. D. P. Williamson, D. B. Shmoys. Approximation Algorithms, Cambridge University Press, 2010, p. 14.